//
// Created by vista on 2017/12/20.
//


#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <set>
using namespace std;

#ifndef NULL
#define NULL 0
#endif

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * newHead , * ptr ;
        newHead = ptr = NULL;

        if(l1 != NULL && l2 != NULL){
            if(l1->val < l2->val){
                newHead = ptr = l1;
                l1 = l1->next;
            }else{
                newHead = ptr = l2;
                l2 = l2->next;
            }
        }else if(l1 != NULL) {
            newHead = ptr = l1;
            l1 = l1->next;
        }else  if(l2 != NULL) {
            newHead = ptr = l2;
            l2 = l2->next;
        }

        while ( l1 != NULL || l2 != NULL)
        {
            if(l1 == NULL)
            {
                ptr->next = l2;
                l2 = l2->next;
            }else if(l2 == NULL){
                ptr->next = l1;
                l1 = l1->next;
            }else{
                if(l1->val <= l2->val){
                    ptr->next = l1;
                    l1 = l1->next;

                }else{
                    ptr->next = l2;
                    l2 = l2->next;
                }
            }
            ptr = ptr->next;
        }

        return newHead;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0)
            return NULL;
        else if(lists.size() == 1){
            return lists[0];
        }else{
            int start = 0;
            ListNode * ptr = lists[start];
            do{
                ptr = mergeTwoLists(ptr,lists[start+1]);
                ++start;
            }while (start < lists.size() - 1);
            return ptr;
        }
    }
};

int main(){

    Solution solution;

    __uint64_t timebegin =  clock_gettime_nsec_np(CLOCK_REALTIME);



    __uint64_t timeend =  clock_gettime_nsec_np(CLOCK_REALTIME);

    cout << (timeend - timebegin) / 1000000.0 << endl;

    return 0;

}